Partizan

Matija Nastasić là sản phẩm của lò đào tạo Partizan. Không thể có được một vị trí trong đội hình Một của Partizan, anh được đem cho mượn sang đội FK Teleoptik thi đấu tại giải hạng 2 Serbia. Ở đó, trung vệ trẻ thuận chân trái đã thi đấu 21 trận và được cựu giám đốc thể thao của Fiorentina ông Pantaleo Corvino để ý đến và ký hợp đồng trong một thương vụ trị giá khoảng 2.5 triệu €.

Fiorentina

Nastasić thi đấu một thời gian ngắn tại đội trẻ Fiorentina, cho đến khi CLB thiếu vị trí trung vệ do thẻ phạt và chấn thương, Nastasić được thể hiện thường xuyên trong đội hình chính. Đồng hương Serbia và là Hlv Fiorentina Siniša Mihajlović đưa anh ra mắt Serie A ngày 11 tháng 9 năm 2011 trong chiến thắng 2-0 trước Bologna. Anh sau đó thi đấu 25 trận trong mùa giải. Một trận đấu anh trở nên nổi bật là trận đấu giữa La Viola với Milan trên SVĐ Artemio Franchi. Nastasić thể hiên chất lượng của mình: tắc bóng hiệu quả, thoải mái khi cầm bóng và óc chiến thuật. Điều đó đã dẫn đến vụ chuyển nhượng vào ngày đóng cửa thị trường chuyển nhượng sang Manchester City trong thương vụ trị giá 15 triệu €, chưa kể đến giá trị của Stefan Savić người chuyển sang Fiorentina theo chiều ngược lại.[2]

Manchester City

Nastasić ký hợp đồng 5 năm với CLB mới Manchester City, cho đến 30 tháng 6 năm 2017. Anh ra mắt trong màu áo CLB mới ngày 18 tháng 9 năm 2012, trong trận đấu Champions League trên sân khách với Real Madrid trên SVĐ Santiago Bernabéu. Anh thi đấu trận đầu tiên tại Premier League ngày 29 tháng Chín trong chiến thắng 2–1 trước Fulham.[3] Anh đảm bảo vị trí của mình trong đội hình ra sân và phong độ cao đã giúp anh nhận danh hiệu Cầu thủ xuất sắc tháng 11 của CLB. Nhanh chóng được CĐV yêu quý,[4] cầu thủ trẻ này đã đẩy cầu thủ 30 tuổi Joleon Lescott ra khỏi vị trí chính thức ở vị trí trung vệ.